#include "headfiles.h"


using namespace std;

LL_NODE_HEAD *addLevelHeadNode(LL_NODE_HEAD *head, 
							   LL_NODE_HEAD *level_head) {
	if (level_head == NULL) {
		cout << "Input argument level_head is NULL!" << endl;
		return NULL;
	}

	if (head == NULL) {
		head = level_head;
	}
	else {
		LL_NODE_HEAD *level = head;
		while (level->next_level) {
			level = level->next_level;
		}

		level->next_level = level_head;
	}

	return head;
}

bool addLevelNode(LL_NODE_HEAD *level_head, LL_NODE *node) {
	if (level_head == NULL ||
		node == NULL) {
		cout << "Input arguments error, NULL!" << endl;
		return false;
	}

	LL_NODE *level = level_head->level;
	if (level == NULL) {
		level_head->level = node;
	}
	else {
		while (level->next) {
			level = level->next;
		}
		level->next = node;
	}

	return true;
}

LL_NODE_HEAD *createLevelLinkList(NODE *root) {
	if (root == NULL) {
		return NULL;
	}

	queue<NODE *> node_queue;
	node_queue.push((NODE *)NULL);
	node_queue.push(root);
	LL_NODE_HEAD *head = NULL;
	LL_NODE_HEAD *level_head = NULL;
	
	while (node_queue.size() > 1) {
		NODE *n = node_queue.front();
		
		// if NULL, it is a new level
		if (n == NULL) {
			level_head = (LL_NODE_HEAD *)malloc(sizeof(LL_NODE_HEAD));
			if (level_head == NULL) {
				cout << "Allocate level head error!" << endl;
			}
			memset(level_head, 0, sizeof(LL_NODE_HEAD));

			head = addLevelHeadNode(head, level_head);

			// pop out the head and push it at the end
			node_queue.pop();
			node_queue.push(n);
		}
		else {
			LL_NODE *level_node = (LL_NODE *)malloc(sizeof(LL_NODE));
			if (level_node == NULL) {
				cout << "Allocate level node error, NULL!" << endl;
			}
			memset(level_node, 0, sizeof(LL_NODE));
			level_node->n = n;

			if (!addLevelNode(level_head, level_node)) {
				cout << "Add level node error!" << endl;
			}
			
			// remove the current node from the queue
			node_queue.pop();
			
			// add it left and right child to the back
			if (n->left) node_queue.push(n->left);
			if (n->right) node_queue.push(n->right);
		}
	}

	// The last node is NULL, clear the queue
	node_queue.pop();

	return head;
}

void printLevelLinkList(LL_NODE_HEAD *head) {
	if (head == NULL) {
		cout << "Empty link list for the tree!" << endl;
		return;
	}

	int level_num = 0;
	LL_NODE *level_node;
	LL_NODE_HEAD *level_head = head;
	while (level_head) {
		++level_num;
		level_head = level_head->next_level;
	}

	cout << "The binary tree has " << level_num << " levels:" << endl;
	level_head = head;
	level_num = 0;
	while (level_head) {
		cout << "Level " << level_num << ": ";
		++level_num;
		level_node = level_head->level;
		while (level_node) {
			cout << "\t" << level_node->n->i;
			level_node = level_node->next;
		}

		level_head = level_head->next_level;
		cout << endl;
	}
}


